import java.util.Arrays;

public class Floyd {
    private static final int INF = 65535;
    public static void main(String[] args) {
        char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
        int[][] matrix = new int[vertex.length][vertex.length];
        matrix[0] = new int[] { 0, 5, 7, INF, INF, INF, 2 };
        matrix[1] = new int[] { 5, 0, INF, 9, INF, INF, 3 };
        matrix[2] = new int[] { 7, INF, 0, INF, 8, INF, INF };
        matrix[3] = new int[] { INF, 9, INF, 0, INF, 4, INF };
        matrix[4] = new int[] { INF, INF, 8, INF, 0, 5, 4 };
        matrix[5] = new int[] { INF, INF, INF, 4, 5, 0, 6 };
        matrix[6] = new int[] { 2, 3, INF, INF, 4, 6, 0 };
        Graph graph = new Graph(vertex,matrix, vertex.length);
        graph.floyd();
        graph.show();
    }
}


class Graph{
    private char[] vertex;//顶点数组
    private int[][] dis;//从各顶点出发到其他顶点的距离
    private int[][] pre;//保存到达目标顶点的前驱结点

    public Graph(char[] vertex, int[][] matrix,int length) {
        this.vertex = vertex;
        this.dis = matrix;
        this.pre = new int[length][length];


        for (int i = 0; i < length; i++) {
            Arrays.fill(pre[i],i);
        }
    }
    public void show(){
        char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
        for (int i = 0; i < vertex.length; i++) {
            for (int j = 0; j < vertex.length; j++) {
                System.out.print("("+vertex[i]+"到"+vertex[j]+"的距离为"+dis[i][j]+")"+" ");
            }
            System.out.println();

            for (int j = 0; j < vertex.length; j++) {
                System.out.print(pre[i][j]+" ");
            }
            System.out.println();
            System.out.println();
        }
    }

    public void floyd(){
        int len=0;
        for (int i = 0; i < vertex.length; i++) {
            for (int j = 0; j < vertex.length; j++) {
                for (int k = 0; k < vertex.length; k++) {
                    len=dis[i][j]+dis[j][k];//i到j的距离加上j到k的距离
                    if (len<dis[i][k]){//如果len小于i到k的距离则更新i到k的最小距离为len
                        dis[i][k]=len;
                        pre[i][k]=pre[j][k];//更新k的前驱节点为j
                    }
                }
            }
        }
    }
}
